package day25;

// NowCoder破译密码——星际密码

// 注意：矩阵幂次方/乘法的计算
// 矩阵的0次方是单位矩阵（主对角线为1）
// 注意：矩阵乘法：第一个矩阵的列==第二个矩阵的行
// 计算时：第一个矩阵的行*第二个矩阵的列（对应相乘后相加！） 【第一个矩阵的行是计算后矩阵的行，第二个矩阵的列是计算后矩阵的列】
// 先自己在草稿纸是上计算几个矩阵，观察各个矩阵做和是哪个角元素，发现：
// 从0次方开始增大过程中：1 1 2 5 7 12... =》观察发现：构成斐波那契数列！！
// 表中数据不超过4位！！ =》模10000

import java.util.Scanner;

public class Main1 {
    // 解码:【重难点！】
    private static void deCoding(int[] arr, int n) {
        for (int i = 0; i < n; i++) {
            int fir = 1; // fib第一个数
            int sec = 1; // fib第二个数
            while (arr[i] > 1) { // 幂次方大于1时才进来计算
                //表中数据如果大于4位，只输出后四位！！ =》方法：模10000 =》余数绝对四位数及以内！
                int ret = (fir + sec)%10000;
                fir = sec;
                sec = ret;
                arr[i]--;
            }
            // 其中一个次幂已经完成，
            // 进行格式化输出（4位，右对齐，不够补0！！）
            System.out.printf("%04d",sec%10000);
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            // 输入数据：组数+次方
            int n = in.nextInt(); // 组数
            int[] arr = new int[n]; // 次方
            for (int i = 0; i < n; i++) {
                arr[i] = in.nextInt();
            }

            // 开始解码
            deCoding(arr,n);
            System.out.println();
        }
    }
}
